The rapid growth in the complexity of modem electronic circuits has forced electronic circuit designers to rely upon computer programs to assist or automate most steps of the design process. Such a design is much too large for a circuit designer or even an engineering team of designers to manage effectively manually. Hence, circuits are almost always designed with the aid of an electronic design automation (EDA) system. Basically, an EDA system is a computer software system used for designing integrated circuit (IC) devices. The EDA system typically receives one or more high level behavioral descriptions of an IC device (e.g., in HDL languages like VHDL, Verilog, etc.) and translates this high level design language description into netlists of various levels of abstraction. At a higher level of abstraction, a generic netlist is typically produced based on technology independent primitives. The generic netlist can be translated into a lower level technology-specific netlist based on a technology-specific library that has gate-specific models for timing and power estimation. A netlist describes the IC design and is composed of nodes (elements) and edges, e.g., connections between nodes, and can be represented using a directed acyclic graph structure having nodes which are connected to each other with signal lines. A single node can have multiple fan-ins and multiple fan-outs. The netlist is typically stored in computer readable media within the EDA system and processed and verified using many well known techniques. One result is a physical device layout in mask form which can be used to directly implement structures in silicon to realize the physical IC device.
The process used to automate the design of electronic circuits entails first producing a high-level description of the circuit in a hardware description language such as Verilog or VHDL. Next, this high-level description is converted into a netlist using a computer implemented synthesis process, such as the “Design Compiler” by Synopsys of Mountain View, Calif. A netlist is a description of the electronic circuit which specifies what cells compose the circuit and which pins of which cells are to be connected together using wires (“nets”). Importantly, the netlist does not specify where on a circuit board or silicon chip the cells are placed or where the wires run which connect them together. Determining this geometric information is the function of an automatic placement process and an automatic routing process, both of which are typically computer programs.
Next, the designer supplies the netlist into the computer implemented automatic cell placement process1. The automatic placement computer program finds a location for each cell on a circuit board or silicon chip. The locations are specified, typically, in two dimensional spatial coordinates, e.g., (x,y) coordinates, on the circuit board or silicon chip. The locations are typically selected to optimize certain objectives such as wire length, wire routability, circuit speed, circuit power consumption, and/or other criteria, subject to the condition that the cells are spread evenly over the circuit board or silicon chip and that the cells do not overlap with each other. The output of the automatic cell placement process includes a data structure including the (x,y) position for each cell of the IC design. Often, the netlist is modified and a new netlist is generated.
Thereupon, the designer supplies the netlist and the cell location data structure, generated by the placement program, to a computer implemented automatic wire routing process. This computer program generates wire geometry within data structure. The wire geometry data structure and cell placement data structure together are used to make the final geometric database needed for fabrication of the circuit as shown by process.
And because circuits today contain hundreds of thousands or even millions of individual pieces or “cells,” placement is done in two steps: a first coarse placement process, followed by detailed a placement process. The coarse placement process assigns a general location for each of the cells (not necessarily legal) within a given boundary and contains interconnect information for connecting the various cells. When selecting the locations of cells, on the one hand, it is desirable to spread cells evenly across the silicon chip or circuit board in order to avoid localized congestion and heat buildup. But on the other hand, it would be desirable to pack cells as tightly as possible in order to minimize wire length, improve speed, and reduce the die size. It is the function of the detailed placement process to take the data structure output by the coarse placement and generate a more detailed placement. (more detailed in the sense that more information is considered such as legal sites). More specifically, the detailed placement process ensures that no cells overlap and that all cells are eventually placed in locations which are located on legal sites. Furthermore, the detailed placement process attempts to optimize the placement of the cells according to desired metrics (e.g., higher density, tighter timing, etc.). Congestion driven placers often leave areas of chip at near 100% density.
One problem encountered with placement in general is that there are virtually countless different ways by which the cells of a given circuit can be arranged. As a result, the task of finding the optimal placement is quite daunting. A course placement and detailed placement process can be run for quite some time in trying to continually optimize a design, with minimal improvements. Eventually, a point of diminishing returns is reached. Another general problem is that course placement and detailed course placement processes have greater difficulty in placing cells at higher densities. Many prior art placement processes simply break down when requested to place cells above certain density levels. In other words, they cannot find solutions exceeding a certain density threshold. Some prior art placement processes can find a high density solution only after running for a significant amount of time or only after an expert human designer “tweaks” the placement. This is disadvantageous as it delays time-to-market and also increases costs.
Accordingly, what is needed is a faster, more efficient placement process. In view of the above needs, the present invention provides a novel cell placement system for increasing the efficiency of an IC design process and which is capable of placing cells with up to 100% density. These and other advantages of the present invention not specifically mentioned above will become clear within discussions of the present invention presented herein.